|
In cryptography, a collision attack on a cryptographic hash tries to find two inputs producing the same hash value, i.e. a hash collision. In contrast to a preimage attack the hash value is not specified. There are roughly two types of collision attacks: ;Collision attack: Find two different messages ''m1'' and ''m2'' such that ''hash(m1)'' = ''hash(m2)''. ;Chosen-prefix collision attack: Given two different prefixes ''p1, p2'' find two appendages ''m1'' and ''m2'' such that ''hash(p1 ∥ m1)'' = ''hash(p2 ∥ m2)'' (where ''∥'' is the concatenation operation). ==Classical collision attack== Mathematically stated, a collision attack finds two different messages ''m1'' and ''m2'', such that ''hash(m1)'' = ''hash(m2)''. In a classical collision attack, the attacker has no control over the content of either message, but they are arbitrarily chosen by the algorithm. Much like symmetric-key ciphers are vulnerable to brute force attacks, every cryptographic hash function is inherently vulnerable to collisions using a birthday attack. Due to the birthday problem, these attacks are much faster than a brute force would be. A hash of ''n'' bits can be broken in 2''n''/2 time (evaluations of the hash function). More efficient attacks are possible by employing cryptanalysis to specific hash functions. When a collision attack is discovered and is found to be faster than a birthday attack, a hash function is often denounced as "broken". The NIST hash function competition was largely induced by published collision attacks against two very commonly used hash functions, MD5〔Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: (Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD ), Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Retrieved July 27, 2008.〕 and SHA-1. The collision attacks against MD5 have improved so much that it takes just a few seconds on a regular computer. Hash collisions created this way are usually constant length and largely unstructured, so cannot directly be applied to attack widespread document formats or protocols. However, workarounds are possible by abusing dynamic constructs present in many formats. In this way, two documents would be created which are as similar as possible in order to have the same hash value. One document would be shown to an authority to be signed, and then the signature could be copied to the other file. Such a malicious document would contain two different messages in the same document, but conditionally display one or the other through subtle changes to the file: * Some document formats like PostScript, or macros in Microsoft Word, have conditional constructs.〔(【引用サイトリンク】title=Hash Collisions (The Poisoned Message Attack) )〕 (if-then-else) that allow testing whether a location in the file has one value or another in order to control what is displayed. *TIFF files can contain cropped images, with a different part of an image being displayed without affecting the hash value.〔 *PDF files are vulnerable to collision attacks by using color value (such that text of one message is displayed with a white color that blends into the background, and text of the other message is displayed with a dark color) which can then be altered to change the signed document's content.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「collision attack」の詳細全文を読む スポンサード リンク
|